#include <iostream>
#include <vector>
#include <deque>
#include <stack>
#include "lib/binary_tree.h"
using namespace std;

void printBinaryTree(BinaryTreeNode* root) {
  if (!root)
    return;
  deque<BinaryTreeNode*> deque_tmp = {root};
  while (!deque_tmp.empty()) {
    auto node = deque_tmp.front();
    cout << node->value << " ";
    deque_tmp.pop_front();
    if (node->left) {
      deque_tmp.push_back(node->left);
    }
    if (node->right) {
      deque_tmp.push_back(node->right);
    }
  }
  cout << endl;
}

void printBinaryTreeByLine(BinaryTreeNode* root) {
  if (!root)
    return;
  deque<BinaryTreeNode*> deque_tmp = {root};
  int cur_line_num = 1;
  int next_line_num = 0;
  while (cur_line_num != 0) {
    auto node = deque_tmp.front();
    cout << node->value << " ";
    deque_tmp.pop_front();
    --cur_line_num;
    if (node->left) {
      deque_tmp.push_back(node->left);
      ++next_line_num;
    }
    if (node->right) {
      deque_tmp.push_back(node->right);
      ++next_line_num;
    }
    if (cur_line_num == 0) {
      cur_line_num = next_line_num;
      next_line_num = 0;
      cout << endl;
    }
  }
}

void printBinaryTreeBySnake(BinaryTreeNode* root) {
  if (!root)
    return;
  vector<stack<BinaryTreeNode*>> stack_vec;
  stack_vec.resize(2);
  stack_vec[0].push(root);
  size_t line_num = 0;
  while (!stack_vec[line_num].empty()) {
    auto node = stack_vec[line_num].top();
    cout << node->value << " ";
    stack_vec[line_num].pop();
    if (line_num == 0) {
      if (node->left) {
        stack_vec[1].push(node->left);
      }
      if (node->right) {
        stack_vec[1].push(node->right);
      }
    } else {
      if (node->right) {
        stack_vec[0].push(node->right);
      }
      if (node->left) {
        stack_vec[0].push(node->left);
      }
    }
    if (stack_vec[line_num].empty()) {
      cout << endl;
      line_num = 1 - line_num;
    }
  }
}

int main() {
  vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  BinaryTreeNode* root = CreateBinaryTree(vec);

  printBinaryTree(root);
  cout << endl;

  printBinaryTreeByLine(root);
  cout << endl;

  printBinaryTreeBySnake(root);
  cout << endl;

  DeleteBinaryTree(root);

  return 0;
}
